package com.shixianjun.sort;

import com.shixianjun.tools.Tools;

public class _6_快速排序 implements Sortable {

    public static void main(String[] args) {
        SortableElement[] arr = {
                new SortableElement(1, 11),
                new SortableElement(1, 10),
                new SortableElement(1, 12),
//                new SortableElement(1, 11),
//                new SortableElement(1, 07),
//                new SortableElement(1, 06),
//                new SortableElement(1, 10),
//                new SortableElement(1, 19),
//                new SortableElement(1, 9),
//                new SortableElement(1, 01),
//                new SortableElement(1, 8),
//                new SortableElement(1, 4),
//                new SortableElement(1, 3),
//                new SortableElement(1, 13),
//                new SortableElement(1, 5),
//                new SortableElement(1, 10),
        };
//        12 12 01 11 07 06 10 19 09 01
        SortableElement.printSortableElementArray("or arr", arr);
        new _6_快速排序().sort(arr);
        SortableElement.printSortableElementArray("so arr", arr);
    }

    @Override
    public void sort(SortableElement[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    void quickSort(SortableElement[] arr, int begin, int end) {
        if (begin >= end) return;

        SortableElement pivot = arr[begin];
        int left = begin + 1, right = end;

        while (left < right) {
            if (left < right && arr[left].value <= pivot.value) left++;
            if (left < right && arr[right].value > pivot.value) right--;

            if (left < right && arr[left].value > pivot.value && arr[right].value <= pivot.value) {
                Tools.swap(arr, left++, right--);
            }
        }

        int index = arr[left].value <= pivot.value ? left : left - 1;
        Tools.swap(arr, index, begin);

        quickSort(arr, begin, index -1);
        quickSort(arr, index + 1, end);
    }
}
